home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / incl / LEDA / impl / ab_tree.h next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  6.3 KB  |  206 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  ab_tree.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef LEDA_AB_TREE_H
  17. #define LEDA_AB_TREE_H
  18.  
  19. //------------------------------------------------------------------------------
  20. //
  21. // (a,b)-trees 
  22. //
  23. // Evelyn Haak, Juergen Dedorath, and Dirk Basenach   (1989)
  24. //
  25. // Implementation follows
  26. // Kurt Mehlhorn : "Data Structures and Algorithms 1", section III, 5.2 - 5.3
  27. //
  28. // Modifications:
  29. // -------------
  30. //
  31. // - member-function insert_at_item added  ( Michael Wenzel , Nov. 89)
  32. //
  33. // - virtual compare function ( Michael Wenzel , Nov. 89)
  34. //
  35. // - delete : overwrite copies of inner nodes by
  36. //            following links between different
  37. //            instances of the same key    ( Michael Wenzel , Jan. 90)
  38. //
  39. // - virtual clear functions  ( S. Naeher, Mai 90)
  40. //
  41. //------------------------------------------------------------------------------
  42.  
  43. #include    <LEDA/basic.h>
  44.  
  45. //------------------------------------------------------------------------------
  46. //  some declarations
  47. //------------------------------------------------------------------------------
  48.  
  49.  
  50. class ab_tree;
  51. class ab_tree_node;
  52.  
  53. typedef ab_tree_node* abnode;
  54.  
  55. typedef ab_tree_node* ab_tree_item;
  56.  
  57.  
  58. /*------------------------------------------------------------*/
  59. /*  class ab_tree_node                                        */
  60. /*------------------------------------------------------------*/
  61.  
  62. class ab_tree_node {
  63.   friend class ab_tree;
  64.  
  65.   friend void concat(ab_tree& s1,ab_tree& s2,ab_tree_node* current,GenPtr cur_key);
  66.   friend void pr_ab_tree(ab_tree_node* localroot,int blancs);
  67.   friend void del_ab_tree(ab_tree_node* localroot);
  68.  
  69.  
  70.   int p;           /* number of sons,a<=p<=b,0 iff leave*/
  71.   int height;      /* height of node*/
  72.   int index;       /* v is index'th son of his father*/
  73.   ab_tree_node* father;   
  74.   GenPtr* k;    /* array[1..b] --------------------------  */
  75.                          //-----------------------------------
  76.                          /*to every node v of T we assign p(v)-1 */
  77.                          /*elements k[1](v),...,k[p(v)-1](v) of U*/
  78.                          /* such that for all i (1<i<p(v)-1):*/
  79.                          /* k[i](v) < k[i+1](v) and for all leaves*/
  80.                          /* w in the i-th subtree of v we have*/
  81.                          /* k[i-1] < key[w] <= k[i](v) */
  82.                          /*------------------------------------*/
  83.                          /* if v is a leave ==> k[1]=key[v]*/
  84.  
  85.                          
  86.   ab_tree_node** son;    /* array [1..b+1] of pointer to sons*/
  87.   ab_tree_node** same;   /* m.w. : links between same keys */
  88.                          /* array [1..b]                   */
  89.   GenPtr inf;
  90.  
  91. /* size = 8 words  */
  92.  
  93. public:
  94.  
  95.   ab_tree_node(int p,int height,int index,ab_tree_node* father,int b);
  96.  
  97.  ~ab_tree_node();
  98.  
  99.   LEDA_MEMORY(ab_tree_node)
  100.  
  101.  }; 
  102.   
  103. /*-----------------------------------------------------------------*/
  104. class ab_tree   
  105.    {
  106.  
  107.     friend class ab_tree_node;
  108.  
  109.     friend void concat(ab_tree&,ab_tree&,ab_tree_node*,GenPtr); 
  110.  
  111.  
  112.     friend void pr_ab_tree(ab_tree_node* localroot,int blancs);
  113.     friend void del_ab_tree(ab_tree_node* localroot);
  114.  
  115.     int a;
  116.     int b;
  117.  
  118.     int height;             /* height of tree   */
  119.     int count;              /* number of leaves */
  120.  
  121.     ab_tree_node* root;
  122.     ab_tree_node* minimum;  
  123.     ab_tree_node* maximum;
  124.  
  125.     ab_tree_node* expand(ab_tree_node* v,int i);
  126.  
  127.     void split_node(ab_tree_node* v);
  128.     void share(ab_tree_node* v,ab_tree_node* y,int direct);
  129.     void fuse (ab_tree_node* v,ab_tree_node* w);
  130.     void del_tree(ab_tree_node* localroot);
  131.     void exchange_leaves(ab_tree_node*, ab_tree_node*);
  132.     void pr_ab_tree(ab_tree_node*,int) const;
  133.  
  134.  
  135.  
  136.     ab_tree_node* copy_ab_tree(ab_tree_node*,abnode&,int) const;
  137.  
  138.     virtual int cmp(GenPtr x, GenPtr y) const { return compare(x,y); }
  139.     virtual void clear_key(GenPtr&) const {}
  140.     virtual void clear_inf(GenPtr&) const {}
  141.     virtual void copy_key(GenPtr&)  const {}
  142.     virtual void copy_inf(GenPtr&)  const {}
  143.     virtual void print_key(GenPtr)  const {}
  144.     virtual void print_inf(GenPtr)  const {}
  145.  
  146. protected:
  147.  ab_tree_item item(void* p) const { return ab_tree_item(p); }
  148.  
  149.  
  150. public:
  151.  
  152.  
  153.  
  154.     void clear();
  155.  
  156.     GenPtr  inf(ab_tree_node* p)  const { return p->inf; }
  157.     GenPtr  key(ab_tree_node* p)  const { return p->k[1]; }
  158.  
  159.     ab_tree_node* insert(GenPtr, GenPtr);
  160.     ab_tree_node* insert_at_item(ab_tree_node*, GenPtr, GenPtr);
  161.     ab_tree_node* locate(GenPtr) const;
  162.     ab_tree_node* locate_succ(GenPtr) const;
  163.     ab_tree_node* locate_pred(GenPtr) const;
  164.     ab_tree_node* lookup(GenPtr) const;
  165.  
  166.     void del(GenPtr);
  167.     void del_item(ab_tree_node*);
  168.     void change_inf(ab_tree_node*, GenPtr);
  169.     void reverse_items(ab_tree_node*, ab_tree_node*);
  170.  
  171.     ab_tree& conc(ab_tree&);
  172.     void split_at_item(ab_tree_node* w,ab_tree& L,ab_tree& R);
  173.  
  174.     void del_min()                 { if (minimum) del_item(minimum); }
  175.     void decrease_key(ab_tree_node* p, GenPtr k) { GenPtr i = p->inf;
  176.                                                 copy_key(i);
  177.                                                 del_item(p);
  178.                                                 insert(k,i);
  179.                                                 clear_key(i);
  180.                                                }
  181.  
  182.  
  183.     bool member(GenPtr k)  const { return (lookup(k))? true: false ; }
  184.  
  185.     ab_tree_node* min()                      const { return minimum; }
  186.     ab_tree_node* find_min()                 const { return minimum; }
  187.     ab_tree_node* max()                      const { return maximum; }
  188.     ab_tree_node* first_item()               const { return minimum; }
  189.     ab_tree_node* next_item(ab_tree_node* p) const { return p->son[2]; }
  190.     ab_tree_node* succ(ab_tree_node* p)      const { return p->son[2]; }
  191.     ab_tree_node* pred(ab_tree_node* p)      const { return p->son[1]; }
  192.  
  193.     int  size()  const { return count;       }
  194.     bool empty() const { return (count==0) ? true : false;   }
  195.     void print() const { pr_ab_tree(root,1); }
  196.  
  197.     ab_tree(int a_=2,int b_=4); 
  198.     ab_tree(const ab_tree& T);
  199.  
  200.     ab_tree& operator=(const ab_tree&);
  201.  
  202.     virtual ~ab_tree(){ clear(); }
  203.  };
  204.  
  205. #endif
  206.